Módulo Redes Sociales: Sesión 5

Departamento de Estadística

Universidad Nacional de Colombia, Sede Bogotá

Equipo de trabajo

Docente del módulo

Monitor del módulo

Código a ejecutar para empezar (de clic en donde en dice “Code”, para desplegar el código, y luego copie y pegue en una sesión abierta de R):

Code
# cambia idioma de la consola de R a español:
Sys.setenv(LANG="es")
# usar 2 cifras significativas y tiende a evitar 
# notación científica (ver ayuda de función: `options`): 
options(digits = 2, scipen = 999) 
# cargar librerías: 
if(!require(igraph)){
  install.packages("igraph"); library(igraph)}
if(!require(sand)){
  install.packages("sand"); library(sand)}

Introducción

Se quiere caracterizar aspectos fundamentales de la estructura social de una red representada por medio de un grafo G=(V,E):

  • Importancia de individuos.
  • Dinámicas sociales.
  • Flujo de la información.
  • Formación de comunidades.

Grado y fuerza

El grado (degree) d_v de un vértice v\in V se define como
d_v=|\left\{\{v,u\}\in E:u\in V \right\}|, i.e., d_v corresponde al número de aristas incidentes en v.

A partir de la matriz de adyacencia \mathbf{Y}=[y_{i,j}] se tiene que el grado del individuo i se puede calcular mediante

d_i = \sum_{i:i\neq j} y_{i,j} = \sum_{j:j \neq i} y_{i,j}\,,\qquad \text{para}\,\,i=1,\ldots,n\,.

El grado de un vértice es la combinación de la sociabilidad y la popularidad.

¿Cómo se adaptan estos conceptos en el caso de los digrafos?

En redes ponderadas, la fuerza (strength) s_v de un vértice v\in V se define como s_v = \sum_{u\in V:\{v,u\}\in E} w_{\{v,u\}}\,, i.e., la suma de los pesos de las aristas incidentes en v.

Ejemplo: Reforma Tributaria en Colombia.

Red de influencia en Twitter (ahora X) sobre la Reforma Tributaria en Colombia, en el contexto de su aprobación en el Congreso.

Estos datos fueron recolectados para estudiar las dinámicas de interacción entre usuarios de la red social, en relación con las opiniones sobre la Reforma Tributaria.

Los usuarios están conectados mediante aristas ponderadas por el número de interacciones (tuits, retuits, citas y comentarios) relacionadas con el tema.

El artículo asociado a estos datos puede ser encontrado aquí.

Ejemplo

Datos

load('out_refTrib.RData')

Grafo

g
IGRAPH ed81599 DN-- 634 755 -- 
+ attr: name (v/c), Grupo (v/n)
+ edges from ed81599 (vertex names):
 [1] DavidRacero   ->Dikarlosy       laurisarabia  ->torres1951     
 [3] MiguelPoloP   ->andrscast       MiguelPoloP   ->gut_benjamin   
 [5] ELTIEMPO      ->ALH_Siyose      petrogustavo  ->chiscohiguera  
 [7] marcelamvz    ->JALEJO1972      ELTIEMPO      ->russo77lds     
 [9] ArgiroCasta888->Juancas35019169 MiguelUribeT  ->RenaldoRicardo 
[11] ghitis        ->JALEJO1972      MiguelPoloP   ->germanquintero 
[13] alertaLatam   ->Johnecheverri5  susanamuhamad ->JRodrigoBolanos
[15] petrogustavo  ->jorgeccruz1     alertaLatam   ->MariaMa40022334
+ ... omitted several edges

Orden

(n <- vcount(g))
[1] 634

Tamaño

ecount(g)
[1] 755

Es dirigida?

is_directed(g)
[1] TRUE

Es ponderada?

is_weighted(g)
[1] FALSE

# matriz de adyacencia
Y <- as_adjacency_matrix(g, sparse = F)
# grado
head(
  cbind(
    degree(graph = g), 
    apply(X = Y, MARGIN = 1, FUN = sum), 
    apply(X = Y, MARGIN = 2, FUN = sum)), n = 5)
             [,1] [,2] [,3]
DavidRacero    10   10    0
laurisarabia   12   12    0
MiguelPoloP    12   12    0
ELTIEMPO        7    7    0
petrogustavo  108  108    0
# grado
d <- degree(graph = g)
head(sort(d, decreasing = T), n = 10)
  petrogustavo   wilsonariasc GustavoBolivar IvanCepedaCast   MiguelUribeT 
           108             45             45             34             31 
   alertaLatam        luiscrh  jarizabaletaf  CeDemocratico      JERobledo 
            31             30             28             27             16 

Top 10 de los participantes de la discusión según el grado.

Visualización

Code
# diseño
set.seed(123)
l <- layout_with_kk(g)
# usando el grado
plot(g, layout = l, vertex.size = 1.5*sqrt(d), vertex.label = NA, vertex.color = adjustcolor("royalblue",0.2), vertex.frame.color = "royalblue", edge.color = adjustcolor("gray",0.4),edge.arrow.size = 0.5)
title(sub = "Grado", line = -1)

Distribución del grado

La distribución del grado (degree distribución) de G es la colección de frecuencia relativas f_0, f_1,\ldots, donde f_d = \frac{|\{v\in V:d_v = d\}|}{|V|}\,,\qquad \text{para}\,\,d=0,1,\ldots\,, i.e., la fracción de vértices en V tales que d_v = d.

La distribución de fuerza (strength distribution) se define de manera análoga.

Visualización

En este gráfico se observa que la mayoría de los individuos tienen un grado bajo, mientras que un grupo reducido presenta un grado elevado. Estos últimos corresponden a figuras altamente influyentes, como el presidente Petro, cuya importancia ya había sido destacada previamente.

Code
par(mfrow = c(1,2))

# Gráfico de barras (distribución del grado)
plot(table(factor(d, levels = 0:n)) / n, type = "h", lwd = 5, 
     xlab = "Grado", ylab = "Densidad", 
     xlim = c(0, max(d)), ylim = c(0, max(table(factor(d, levels = 0:n)) / n)), 
     main = "", xaxt = "n", col = "gray50")
axis(side = 1, at = seq(from = 0, to = max(d), by = 5))  # Ajustar el eje x automáticamente

# Histograma (densidad del grado)
plot(NA, NA, type = "n", xlim = c(min(d), max(d)), ylim = c(0, 0.4), xlab = "Grado", ylab = "Densidad", main = "")
hist(d, freq = FALSE, col = "gray90", border = "gray50",add =T)

# Título general
title(main = "Distribución del grado", outer = TRUE, line = -2)

Ley de potencias

En algunas redes se tiene que una gran porción de vértices tiene grado bajo y una pequeña fracción tiene grado alto. Esta pequeña fracción de vértices se conoce como centros (hubs).

En estos casos la distribución del grado tiene una cola larga a la derecha. Esto se traduce en un decaimiento aproximadamente lineal en la frecuencia logarítmica en función del grado logarítmico.

La distribución de la ley de potencias (power law distribution) señala que la distribución del grado d es de la forma f_d = \mathrm{c}\,d^{-\alpha}\,,\qquad \mathrm{c}>0\,,\qquad \alpha>1\,, lo que en escala log corresponde a \log f_d = \log \mathrm{c} - \alpha\log d\,. \mathrm{c} se denomina constante de normalización y \alpha exponente de la ley de potencias (similar a la distribución de Pareto).

Libre de escala

Las redes que satisfacen este tipo de distribución del grado se denominan libres de escala (scale free) dado que f_{a\,d} = \mathrm{c}\, (a\,d)^{-\alpha} = a^{-\alpha}\,f_d\,. En una red libre de escala, algunos nodos están altamente conectados, es decir, poseen un gran número de enlaces a otros nodos, aunque el grado de conexión de casi todos los nodos es bastante bajo.

Distribución de Grados y Conectividad Local

  • Distribución de grado
dd <- degree_distribution(g)
  • Grado promedio de los vecinos (GPV) más cercados de orden 1
mnd <- knn(graph = g, vids = V(g))$knn
mean(d[as.numeric(neighbors(graph = g, v = 1))])
[1] 2.2

Visualización

Code
par(mfrow = c(1,2))
plot(NA, NA, type = "n", xlim = c(0,110), ylim = c(0,0.1), xlab = "Grado", ylab = "Densidad", main = "Distribución de grado")
hist(d, freq = F, col = "lightskyblue", border = "royalblue", add = T)
plot((0:max(d))[dd != 0], dd[dd != 0], log = "xy", pch = 16, col = adjustcolor("royalblue", 0.5), xlab = "Log-grado", ylab = "Log-densidad", main = "Distribución de grado (log-log)")

Visualización: GPV vs. grado

Code
plot(x = d, y = mnd, log = "xy", pch = 16, col = adjustcolor("yellow3", 0.5), xlab = "Log-grado", ylab = "Log-grado promedio de los vecinos")

Centralidad

Las medidas de centralidad están diseñadas para cuantificar la “importancia” de los nodos de una red.

  • Centralidad de cercanía (closeness centrality).
  • Centralidad de intermediación (betweenness centrality).
  • Centralidad propia (eigenvector centrality).

Existen versiones normalizadas de todas las medidas para facilitar la comparación entre grafos y otras medidas. La normalización se logra multiplicando por una constante apropiada.

Existen versiones para redes dirigidas y ponderadas.

Centralidad de cercanía

Un vértice se considera “importante” si está “cerca” de muchos otros vértices: c_{\textsf{C}}(v) = \frac{1}{\sum_{u\in V} \textsf{d}(v,u)} donde \textsf{d}(v,u) es la distancia geodésica entre los vértices u y v de V.

ejemplo

# distancias
D <- distances(graph = g)
# closeness centraliy no normalizada
head(
  cbind(
    closeness(graph = g, normalized = F), 
    1/apply(X = D, MARGIN = 1, FUN = sum), 
    1/apply(X = D, MARGIN = 2, FUN = sum)), n = 5)
               [,1]    [,2]    [,3]
DavidRacero  0.1000 0.00028 0.00028
laurisarabia 0.0833 0.00028 0.00028
MiguelPoloP  0.0833 0.00018 0.00018
ELTIEMPO     0.1429 0.00023 0.00023
petrogustavo 0.0093 0.00031 0.00031
# closeness centraliy normalizada
n <- vcount(g)
head(
  cbind(
  closeness(graph = g, normalized = T), 
  (n - 1)/apply(X = D, MARGIN = 1, FUN = sum), 
  (n - 1)/apply(X = D, MARGIN = 2, FUN = sum)), n = 5)
             [,1] [,2] [,3]
DavidRacero     1 0.18 0.18
laurisarabia    1 0.18 0.18
MiguelPoloP     1 0.11 0.11
ELTIEMPO        1 0.14 0.14
petrogustavo    1 0.20 0.20
# top 5
cc <- closeness(graph = g, normalized = T)
head(sort(cc, decreasing = T), n = 5)
 DavidRacero laurisarabia  MiguelPoloP     ELTIEMPO petrogustavo 
           1            1            1            1            1 

Centralidad de intermediación

Un vértice se considera “importante” si se encuentra “entre” otros pares de vértices.

Los vértices que se encuentran en muchos caminos son más críticos para el proceso de comunicación: c_{\textsf{B}}(v) = \sum_{s,t\in V:s\neq t\neq v} \frac{\sigma(s,t\mid v)}{\sigma(s,t)} donde \sigma(s,t\mid v) es el número total de caminos más cortos entre s y t que pasan por v, y \sigma(s,t) es el número total de caminos más cortos entre s y t (independientemente de si pasan por v o no).

# betweenness centraliy no normalizada
head(x = betweenness(graph = g, normalized = F), n = 5)
 DavidRacero laurisarabia  MiguelPoloP     ELTIEMPO petrogustavo 
           0            0            0            0            0 
# betweenness centrality normalizada
n <- vcount(g)
head(
  cbind(
    betweenness(graph = g, normalized = F)/((n-1)*(n-2)/2), 
    betweenness(graph = g, normalized = T)), n = 5)
             [,1] [,2]
DavidRacero     0    0
laurisarabia    0    0
MiguelPoloP     0    0
ELTIEMPO        0    0
petrogustavo    0    0
# top 5
bc <- betweenness(graph = g, normalized = T)
head(sort(bc, decreasing = T), n = 5)
   Mamertos0  DavidRacero laurisarabia  MiguelPoloP     ELTIEMPO 
     0.00001      0.00000      0.00000      0.00000      0.00000 

Centralidad propia

Un vértice se considera “importante” si sus vecinos son a su vez “centrales”: c_{\textsf{E}}(v) = \alpha\sum_{\{u,v\}\in E} c(u) donde \mathbf{c}=(c(1),\ldots,c(n)) es una solución al problema de vectores propios dado por \mathbf{Y}\mathbf{c}=\alpha^{-1}\mathbf{c}, con \mathbf{Y} la matriz de adyacencia, \alpha^{-1} es el valor propio más grande de \mathbf{Y}, y \mathbf{c} es el vector propio correspondiente.

La convención es reportar los valores absolutos de las entradas de \mathbf{c}.

Ejemplo

# matriz de adyacencia
Y <- as_adjacency_matrix(g, sparse = F)
g <- graph_from_adjacency_matrix(Y)
evd <- eigen(Y)
# eigen centraliy no normalizada
head(
  cbind(
    eigen_centrality(graph = g, scale = F)$vector,
    eigen_centrality(graph = g, scale = F)$vector,
    Y%*%c(1/evd$values[1]*(-1)*evd$vectors[,1])), n = 5)  # vector propio x (-1)
                     [,1]         [,2] [,3]
DavidRacero  0.0189891682 0.0189891682  NaN
laurisarabia 0.0135271692 0.0135271692  NaN
MiguelPoloP  0.0000000031 0.0000000031  NaN
ELTIEMPO     0.0064981914 0.0064981914  NaN
petrogustavo 0.6718769980 0.6718769980  NaN
# eigen centraliy normalizada
head(
  cbind(
    eigen_centrality(graph = g, scale = T)$vector,
    eigen_centrality(graph = g, scale = T)$vector,
    Y%*%c(1/evd$values[1]*(-1)*evd$vectors[,1])/max(Y%*%c(1/evd$values[1]*(-1)*evd$vectors[,1]))), n = 5)
                     [,1]         [,2] [,3]
DavidRacero  0.0282628640 0.0282628640  NaN
laurisarabia 0.0201334013 0.0201334013  NaN
MiguelPoloP  0.0000000046 0.0000000046  NaN
ELTIEMPO     0.0096716979 0.0096716979  NaN
petrogustavo 1.0000000000 1.0000000000  NaN
# top 5
ec <- eigen_centrality(graph = g, scale = T)$vector
head(sort(ec, decreasing = T), n = 5)
  petrogustavo   wilsonariasc IvanCepedaCast GustavoBolivar    Fabijarabar 
          1.00           0.19           0.16           0.15           0.14 

Code
# medidas de centralidad
dc <- degree          (graph = g, normalized = T)
cc <- closeness       (graph = g, normalized = T)
cc[is.na(cc)] <- 0
bc <- betweenness     (graph = g, normalized = T)
ec <- eigen_centrality(graph = g, scale = T)$vector
# visualizacion
par(mfrow = c(2,2), mar = c(4, 3, 3, 1))
set.seed(123)
plot(g, layout = l, vertex.size = 15*sqrt(dc), vertex.frame.color = "black", vertex.label = NA, main = "Grado",edge.arrow.size = 0.2)
plot(g, layout = l, vertex.size = 5*sqrt(cc), vertex.frame.color = "black", vertex.label = NA, main = "Cercania",edge.arrow.size = 0.2)
plot(g, layout = l, vertex.size = 15*sqrt(bc), vertex.frame.color = "black", vertex.label = NA, main = "Intermediación",edge.arrow.size = 0.2)
plot(g, layout = l, vertex.size = 15*sqrt(ec), vertex.frame.color = "black", vertex.label = NA, main = "Propia",edge.arrow.size = 0.2)